/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 * 示例 1：
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 *
 * 示例 2：
 * 输入：l1 = [], l2 = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 */

/**
 * 1. 暴力法, 创建一个新链表, 一点一点遍历链表, 然后比较大小, 将先小一点节点放入新建的新链表中
 * 注意结束的时候判断一下谁先为空, 然后再将不为空的链表尾插进新建的链表中
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 *
 * 2. 递归法 我们知道排序肯定是一个一个进行的, 首先我们先排第一个数, 这个数排好也就相当于这个数已经有顺序了
 * 后面我们在去排除这个之外的数, 可以发现后面的步骤和之前的思路是一样的, 这也就让我们可以使用递归来解决这道问题
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {

    // ********************************************************
    // 1.暴力法
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {

        // 创建虚拟节点
        ListNode newHead = new ListNode(0);

        // 打工仔登场
        ListNode cur = newHead;

        // 有一个来链表先全部判断完就结束
        while (list1 != null && list2 != null) {


            // 那个节点的值小先将谁尾插入新链表
            if (list1.val < list2.val) {

                cur.next = list1;
                cur = list1;
                list1 = list1.next;

            } else {

                cur.next = list2;
                cur = list2;
                list2 = list2.next;

            }
        }

        // 记得将不为空的链表直接尾插进新链表
        if (list1 == null) {
            cur.next = list2;
        } else {
            cur.next = list1;
        }

        // 返回结果
        return newHead.next;
    }

    // *********************************************************
    // 2.递归法
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        // 递归出口
        // 如果递归到某条链表的结尾, 说明前面的都已经排序了, 我们只需要将
        // 剩下的一条没有遍历完的链表遍历结束, 也就是将他尾插进前面的链表就行了,
        // 所以只要返回剩下的一条链表就可以了
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        // 这里比较一下该节点的值大小
        if (list1.val <= list2.val) {

            // 要是 list1 的节点小, 那么最后返回的也是 list1,
            // 若是 list2 的节点小, 也是返回 list2
            // 这里接着向下遍历, 第一个已经排好了序, 排剩下的序,
            // 并将后面排好的尾插进 list1
            // 后面的步骤也是一样的, 直到进入递归出口
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
